class QuickSort {
  quickSort(arr, startIndex, endIndex) {
    if(startIndex >= endIndex) {
      return arr
    }
    let pivotIndex = this.partition(arr, startIndex, endIndex)
    this.quickSort(arr, startIndex, pivotIndex-1)
    this.quickSort(arr, pivotIndex+1, endIndex)
  }
  partition(arr, startIndex, endIndex) {
    let pivot = arr[startIndex]
    let mark = startIndex
    for(let i = startIndex+1; i<=endIndex; i++){
      if(arr[i]<pivot){
        mark++
        let p = arr[mark]
        arr[mark] = arr[i]
        arr[i] = p
      }
    }
    arr[startIndex] = arr[mark]
    arr[mark] = pivot
    return mark
  }
}

let arr = [4,4,6,5,3,2,8,1]
let quicksort = new QuickSort()
let quick =quicksort.quickSort(arr, 0, arr.length-1)
console.log(quick)